package Tree;

import java.util.ArrayList;
import java.util.List;

public class _199_BinaryTreeRightSideView {
    //traversal every level
    List<Integer> res = new ArrayList<>();
    public List<Integer> rightSideView_1(TreeNode root) {
        if(root==null) return res;
        List<TreeNode> tnode = new ArrayList<>();
        tnode.add(root);
        while (!tnode.isEmpty()) {
            List<TreeNode> tempNode = new ArrayList<>();
            for (TreeNode t : tnode) {
                if (t.left != null) {
                    tempNode.add(t.left);
                }
                if (t.right != null) {
                    tempNode.add(t.right);
                }
            }
            res.add(tnode.get(tnode.size() - 1).val);
            tnode = tempNode;
        }
        return res;
    }

    //solution 2:use recursion and deep-first search,mark every level.
    public List<Integer> rightSideView(TreeNode root) {
        helper(root, 1);
        return res;
    }
    public void helper(TreeNode root, int level) {
        if (root != null) {
            if (res.size() < level) {
                res.add(root.val);
            }
            helper(root.right, level + 1);
            helper(root.left, level + 1);
        }
    }
}
